/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.dubbo.rpc.cluster.loadbalance;

import org.apache.dubbo.common.URL;
import org.apache.dubbo.common.utils.StringUtils;
import org.apache.dubbo.rpc.Invocation;
import org.apache.dubbo.rpc.Invoker;
import org.apache.dubbo.rpc.cluster.ClusterInvoker;
import org.apache.dubbo.rpc.support.RpcUtils;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

import static org.apache.dubbo.common.constants.CommonConstants.TIMESTAMP_KEY;
import static org.apache.dubbo.common.constants.RegistryConstants.REGISTRY_SERVICE_REFERENCE_PATH;
import static org.apache.dubbo.rpc.cluster.Constants.WEIGHT_KEY;

/**
 * This class select one provider from multiple providers randomly.
 * You can define weights for each provider:
 * If the weights are all the same then it will use random.nextInt(number of invokers).
 * If the weights are different then it will use random.nextInt(w1 + w2 + ... + wn)
 * Note that if the performance of the machine is better than others, you can set a larger weight.
 * If the performance is not so good, you can set a smaller weight.
 */
public class RandomLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "random";

    /**
     * Select one invoker between a list using a random criteria
     *
     * @param invokers   List of possible invokers
     * @param url        URL
     * @param invocation Invocation
     * @param <T>
     * @return The selected invoker
     */
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // Number of invokers invoker的数量
        int length = invokers.size();
        // 若不需要加权负载均衡，则直接生成一个[0, length)的随机数，选择出invoker
        if (!needWeightLoadBalance(invokers, invocation)) {
            return invokers.get(ThreadLocalRandom.current().nextInt(length));
        }

        // Every invoker has the same weight? 每个invoker是否有相同权重
        boolean sameWeight = true;
        // the maxWeight of every invoker, the minWeight = 0 or the maxWeight of the last invoker
        // 记录当前invoker及其前面所有invoker的权重之和
        int[] weights = new int[length];
        // The sum of weights 记录每个invoker和之前所有所有invoker的权重之和，并且判断所有invoker的权重是否都相同
        int totalWeight = 0;
        for (int i = 0; i < length; i++) {
            int weight = getWeight(invokers.get(i), invocation);
            // Sum
            totalWeight += weight;
            // save for later use 记录前i+1个(包含第i+1个)所有主机的权重之和
            weights[i] = totalWeight;
            //判断主机权重相同 并前i+1个主机权重之和不等于第i+1个主机的权重乘以i+1
            if (sameWeight && totalWeight != weight * (i + 1)) {
                sameWeight = false;//说明权重不同
            }
        }
        // 处理各invoker的权重不同的情况
        if (totalWeight > 0 && !sameWeight) {
            // If (not every invoker has the same weight & at least one invoker's weight>0), select randomly based on
            // totalWeight.
            // 生成一个随机权重[0, totalWeight)之间
            int offset = ThreadLocalRandom.current().nextInt(totalWeight);
            // Return an invoker based on the random value.
            if (length <= 4) {//invoker数量小于等于4个，直接循环比较，找出比随机权重大的最小权重和i
                for (int i = 0; i < length; i++) {
                    if (offset < weights[i]) {
                        return invokers.get(i);//获取对应位置的invoker
                    }
                }
            } else {
                //二分查找,找出
                int i = Arrays.binarySearch(weights, offset);
                if (i < 0) {
                    i = -i - 1;
                } else {//刚好某个i总权重之和等于随机权重，
                    //再判断第i+1个权重和随机权重是否相等，如果相等，代表后面的提供者主机权重为0，并且i++，继续循环
                    //直到找到比随机权重大的最小权重和
                    while (weights[i + 1] == offset) {
                        i++;
                    }
                    i++;//i再增加1位
                }
                return invokers.get(i);//获取对应位置的invoker
            }
        }
        // If all invokers have the same weight value or totalWeight=0, return evenly.
        // 处理各invoker权重相同的情况(与无权重的处理方式相同）
        return invokers.get(ThreadLocalRandom.current().nextInt(length));
    }

    private <T> boolean needWeightLoadBalance(List<Invoker<T>> invokers, Invocation invocation) {
        Invoker<T> invoker = invokers.get(0);
        URL invokerUrl = invoker.getUrl();
        if (invoker instanceof ClusterInvoker) {
            invokerUrl = ((ClusterInvoker<?>) invoker).getRegistryUrl();
        }
        //  Multiple registry scenario, load balance among multiple registries.
        //  判断调用的服务时org.apache.dubbo.registry.RegistryService服务
        if (REGISTRY_SERVICE_REFERENCE_PATH.equals(invokerUrl.getServiceInterface())) {
            String weight = invokerUrl.getParameter(WEIGHT_KEY);
            return StringUtils.isNotEmpty(weight);
        } else {
            String weight = invokerUrl.getMethodParameter(RpcUtils.getMethodName(invocation), WEIGHT_KEY);
            if (StringUtils.isNotEmpty(weight)) {
                return true;
            } else {//如果没配置权重，并且
                String timeStamp = invoker.getUrl().getParameter(TIMESTAMP_KEY);
                return StringUtils.isNotEmpty(timeStamp);
            }
        }
    }
}
